package graphic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
* 给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

示例：



输入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/clone-graph
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class CloneGraph {

    class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }

        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }

//    public Node cloneGraph(Node node) {
//        if(node == null){
//            return null;
//        }
//        Map<Node, Node> visited = new HashMap<>();
//        return dfs(node, visited);
//    }
//
//    private Node dfs(Node node, Map<Node, Node> visited){
//        Node newNode = new Node();
//        newNode.val = node.val;
//        newNode.neighbors = new ArrayList<>();
//        visited.put(node, newNode);
//        for(Node n: node.neighbors){
//            if(visited.containsKey(n)) {
//                newNode.neighbors.add(visited.get(n));
//            } else {
//                newNode.neighbors.add(dfs(n, visited));
//            }
//        }
//        return newNode;
//    }

    public Node cloneGraph(Node node) {
        if(node == null){
            return node;
        }
        Map<Node, Node> visited = new HashMap<>();
        return dfs(node, visited);
    }

    private Node dfs(Node node, Map<Node, Node> visited){
        if(visited.containsKey(node)){
            return visited.get(node);
        }
        Node clone = new Node(node.val);
        visited.put(node, clone);
        for(Node nei: node.neighbors){
            Node cloneNei = dfs(nei, visited);
            clone.neighbors.add(cloneNei);
        }
        return clone;
    }
}
